contents

네, 카르노 맵(K-map)에 대한 설명을 한국어로 번역해 드리겠습니다.

카르노 맵(Karnaugh map, K-map) 은 불 대수 표현식을 단순화하는 데 사용되는 그래픽 방법입니다. 이는 불 함수의 항과 변수의 수를 최소화하는 데 도움을 주는 시각적 도구로, 결과적으로 디지털 회로에 필요한 논리 게이트의 수를 줄여 회로를 더 간단하고 저렴하게 만듭니다.

카르노 맵은 본질적으로 진리표를 재배치한 것으로, 값들이 2차원 그리드에 배치됩니다. 이 맵의 독창성은 고유한 순서 배열에 있으며, 이를 통해 논리적 인접성을 시각적으로 발견하고 표현식을 단순화할 수 있습니다.

핵심 원리: 그레이 코드

카르노 맵의 결정적인 특징은 행과 열이 그레이 코드(Gray code) 로 정렬된다는 것입니다. 그레이 코드에서는 인접한 두 셀 사이에 단 하나의 비트만 변경됩니다. 이 인접성에는 맵의 "순환"하는 가장자리도 포함됩니다 (윗부분 가장자리는 아랫부분 가장자리와 인접하고, 왼쪽 가장자리는 오른쪽 가장자리와 인접합니다).

이 단일 비트 변경 규칙이 바로 단순화를 가능하게 하는 원리입니다. 만약 두 인접한 셀이 모두 '1'을 포함하고 있다면, 이는 해당하는 불 대수 항들이 단 하나의 변수에서만 차이가 남을 의미하며, 이 변수는 제거될 수 있습니다.

카르노 맵을 이용한 단순화 방법

과정은 몇 가지 간단한 단계로 이루어집니다.

1. 맵 생성: 셀들의 그리드를 그립니다. _n_개의 변수에 대해 2ⁿ개의 셀이 필요합니다. 4개의 변수(A, B, C, D)의 경우, 4x4 그리드가 됩니다.
2. 맵 채우기: 불 함수나 진리표의 출력에 따라 맵을 1과 0으로 채웁니다.
3. '1' 그룹화하기: 이것이 핵심 단계입니다.
   • 인접한 '1'들의 그룹을 원으로 묶습니다.
   • 그룹은 반드시 직사각형이어야 하며, 2의 거듭제곱 개수(1, 2, 4, 8, 16...)의 셀을 포함해야 합니다.
   • 그룹을 가능한 한 크게 만드세요.
   • 그룹은 서로 겹쳐도 됩니다.
   • 순환하는 인접성을 기억하세요.
4. 단순화된 항 유도하기: 각 그룹에 대해, 그 그룹 내에서 변하지 않는 변수(들)를 찾습니다. 이 고정된 변수들이 해당 그룹의 단순화된 항을 형성합니다.
5. 최종 표현식: 최종 단순화된 표현식은 모든 그룹에서 유도된 항들의 합(논리적 OR)입니다.

예제: 4변수 카르노 맵

다음과 같은 최소항(minterm)의 합으로 주어진 불 함수 F(A, B, C, D)를 단순화해 보겠습니다.

F(A, B, C, D) = Σm(0, 2, 5, 7, 8, 10, 13, 15)

이는 이진 입력 0000, 0010, 0101, 0111, 1000, 1010, 1101, 1111에 대해 함수의 출력이 '1'임을 의미합니다.

1 & 2단계: 맵 생성 및 채우기

4x4 그리드를 만듭니다. 행은 변수 AB를, 열은 CD를 나타냅니다. 그레이 코드 순서(00, 01, 11, 10)를 사용하여 레이블을 지정하고 명시된 최소항에 해당하는 셀에 1을 채웁니다.

      CD
      00  01  11  10
    +---+---+---+---+
 00 | 1 | 0 | 0 | 1 |
    +---+---+---+---+
 01 | 0 | 1 | 1 | 0 |
AB  +---+---+---+---+
 11 | 0 | 1 | 1 | 0 |
    +---+---+---+---+
 10 | 1 | 0 | 0 | 1 |
    +---+---+---+---+

3단계: '1' 그룹화하기

이제 인접한 '1'들로 만들 수 있는 가장 큰 그룹들을 식별합니다. 이 맵에서는 두 개의 그룹을 만들 수 있습니다.

• 파란색 그룹: 네 개의 모서리(최소항 0, 2, 8, 10)를 포함합니다. 이는 순환 인접성의 대표적인 예입니다. 맨 위 행은 맨 아래 행과 인접하고, 맨 왼쪽 열은 맨 오른쪽 열과 인접합니다.
• 빨간색 그룹: 중앙에 있는 네 개의 '1'(최소항 5, 7, 13, 15)을 포함합니다. 이는 수직 및 수평 인접성을 모두 보여줍니다.

그룹을 문자로 표시한 맵은 다음과 같습니다. (B: 파란색 그룹, R: 빨간색 그룹)

      CD
      00  01  11  10
    +---+---+---+---+
 00 | B |   |   | B |
    +---+---+---+---+
 01 |   | R | R |   |
AB  +---+---+---+---+
 11 |   | R | R |   |
    +---+---+---+---+
 10 | B |   |   | B |
    +---+---+---+---+

4단계: 단순화된 항 유도하기

이제 각 그룹을 분석하여 어떤 변수가 일정한지 확인합니다.

• 파란색 그룹(B) (m0, m2, m8, m10) 분석:
  • 행 변수 (A, B)를 봅시다: 그룹이 00(A'B')과 10(AB') 행에 걸쳐 있습니다. A의 값은 0에서 1로 변하지만, B의 값은 0으로 일정합니다 (B').
  • 열 변수 (C, D)를 봅시다: 그룹이 00(C'D')과 10(CD') 열에 걸쳐 있습니다. C의 값은 0에서 1로 변하지만, D의 값은 0으로 일정합니다 (D').
  • 따라서 파란색 그룹의 단순화된 항은 B'D' 입니다.
• 빨간색 그룹(R) (m5, m7, m13, m15) 분석:
  • 행 변수 (A, B)를 봅시다: 그룹이 01(A'B)과 11(AB) 행에 걸쳐 있습니다. A의 값은 0에서 1로 변하지만, B의 값은 1로 일정합니다 (B).
  • 열 변수 (C, D)를 봅시다: 그룹이 01(C'D)과 11(CD) 열에 걸쳐 있습니다. C의 값은 0에서 1로 변하지만, D의 값은 1로 일정합니다 (D).
  • 따라서 빨간색 그룹의 단순화된 항은 BD 입니다.

5단계: 최종 표현식

최종 단순화된 표현식은 모든 그룹의 항들을 OR 연산한 것입니다.

F(A, B, C, D) = B'D' + BD

이 단순화된 표현식은 원래의 훨씬 긴 표현식과 논리적으로 동일하지만, 회로로 구현할 때 훨씬 적은 수의 논리 게이트를 필요로 합니다.

references